package cn.nawang.ebeim.client.version;

/**
 * Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
 * For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
 * the contiguous subarray [4,−1,2,1] has the largest sum = 6.
 * <p>
 * Created by GanJc on 2016/2/26.
 */
public class MaximumSubarray {

    public static void main(String[] args) {
        int a[] = {-2, -3};
        int b[] = {-2,1,-3,4,-1,2,1,-5,4};
        maximumSubArray(a);
        maximumSubArray(b);
    }

    //dp[i + 1] = max(dp[i], dp[i] + a[i + 1])
    public static int maximumSubArray(int a[]) {
        int max = a[0];
        for (int i = 0, sum = 0; i < a.length; i++) {
            sum += a[i];
            max = Math.max(sum, max);
            if (sum < 0) sum = 0;
        }
        System.out.println(max);
        return max;
    }


}
